package zuochengyun;

import java.util.HashMap;


//TopKOfTimes的进阶问题
//逐渐的加入记录，要判断topK
//TopKOfTimes2 object = new TopKOfTimes2(k);	//代印topK问题
//object.add("A");
//object.printTopK();
public class TopKOfTimes2 {

	// 使用堆的方式来完成
	private class HeapNode {
		public String str; // 值
		public int times; // 来自哪个数组

		public HeapNode(String str, int times) {
			this.str = str;
			this.times = times;
		}
	}

	private HeapNode[] heap;
	private int index;
	private HashMap<String, HeapNode> strNodeMap;	//字符串到结点的映射
	private HashMap<HeapNode, Integer> nodeIndexMap;	//用来判断该结点是否在堆中，为-1表示不再，其他表示堆中的下标
	
	private TopKOfTimes2(int k){
		heap = new HeapNode[k];
		index = 0;
		strNodeMap = new HashMap<>();
		nodeIndexMap = new HashMap<>();
	}
	
	public void add(String str){
		HeapNode curNode = null;
		int preIndex = -1;	//该结点在堆中的下标，为-1表示不在
		if(!strNodeMap.containsKey(str)){
			curNode = new HeapNode(str, 1);
			strNodeMap.put(str, curNode);
			nodeIndexMap.put(curNode, -1);	//-1表示不在堆结构中
		}else{
			curNode = strNodeMap.get(str);
			curNode.times++;
			strNodeMap.put(str, curNode);
			//如果之前就在堆中，那么加1之后肯定还是topK
			preIndex = nodeIndexMap.get(curNode);
		}
		if(preIndex == -1){
			if(index == heap.length){
				//如果堆已满
				if(heap[0].times < curNode.times){
					nodeIndexMap.put(heap[0], -1);	//将heap[0]从堆中移除了
					nodeIndexMap.put(curNode, 0);	//将curNode添加到堆中
					heap[0] = curNode;
					heapAdjust(heap, 0, index);
				}
			}else{
				nodeIndexMap.put(curNode, index);	//将curNode添加到堆中
				heap[index] = curNode;
				heapCreate(heap, index++);
			}
		}else{
			//此时只需要进行堆的调整即可
			heapAdjust(heap, preIndex, index);
		}
	}
	
	//此时不需要严格地排序
	public void printTopK(){
		System.out.println("Top :");
		for (int i = 0; i < heap.length; i++) {
			if(heap[i] == null){
				break;
			}
			System.out.println("str:" + heap[i].str);
			System.out.println("times:" + heap[i].times);
		}
	}
	
	private void heapAdjust(HeapNode[] heap, int index, int heapSize) {
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		int small = index;
		while (left < heapSize) {
			if (heap[left].times < heap[index].times) {
				small = left;
			}
			if (right < heapSize && heap[right].times < heap[left].times) {
				small = right;
			}
			if (small != index) {
				swap(heap, index, small);
			} else {
				break;
			}
			index = small;
			left = index * 2 + 1;
			right = index * 2 + 2;
		}
	}

	public void heapCreate(HeapNode[] heap, int index) {
		while (index != 0) {
			int parent = (index - 1) / 2;
			if (heap[parent].times > heap[index].times) {
				swap(heap, parent, index);
				index = parent;
			} else {
				break;
			}
		}
	}

	public void swap(HeapNode[] heap, int index1, int index2) {
		HeapNode temp = heap[index1];
		heap[index1] = heap[index2];
		heap[index2] = temp;
		//由于nodeIndexMap记录堆中结点的下标，所以每次更换都要更新
		nodeIndexMap.put(heap[index1], index2);
		nodeIndexMap.put(heap[index2], index1);
	}
	
}
